package main

import "sort"

func twoSum0(nums []int, target int) [][]int {
	left := 0
	right := len(nums) - 1
	ans := make([][]int, 0)
	for left < right {
		leftVal := nums[left]
		rightVal := nums[right]
		sum := leftVal + rightVal
		if sum < target {
			for left < right && nums[left] == leftVal {
				left++
			}
		} else if sum > target {
			for left < right && nums[right] == rightVal {
				right--
			}
		} else {
			ans = append(ans, []int{nums[left], nums[right]})
			for left < right && nums[left] == leftVal {
				left++
			}
			for left < right && nums[right] == rightVal {
				right--
			}
		}
	}
	return ans
}

func fourSum(nums []int, target int) [][]int {
	if len(nums) < 4 {
		return nil
	}
	sort.Slice(nums, func(i, j int) bool {
		return nums[i] < nums[j]
	})
	ans := make([][]int, 0)
	for i := 0; i < len(nums)-1; i++ {
		for j := i + 1; j < len(nums)-1; j++ {
			target0 := target - nums[i] - nums[j]
			twoSumAns := twoSum0(nums[j+1:], target0)
			if len(twoSumAns) == 0 {
				continue
			}
			for _, pair := range twoSumAns {
				anAns := []int{
					nums[i],
					nums[j],
					pair[0],
					pair[1],
				}
				ans = append(ans, anAns)
			}
			for j < len(nums)-1 && nums[j] == nums[j+1] {
				j++
			}
		}
		for i < len(nums)-1 && nums[i] == nums[i+1] {
			i++
		}
	}
	return ans
}

func main() {
	ans := fourSum([]int{-2, -1, -1, 1, 1, 2, 2}, 0)
	println(ans)
}
